package algorithm.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三角形最小路径和 {
    // 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
    //
    // 例如，给定三角形：
    //
    // [
//     [2],
//    [3,4],
//   [6,5,7],
//  [4,1,8,3]
    // [2],
    // [3,4],
    // [6,5,7],
    // [4,1,8,3]
    // ]
    // 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
    //
    // 说明：
    //
    // 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] cost = new int[len + 5];
        for (List<Integer> list : triangle) {
            for (int i = list.size() - 1; i >= 0; i--) {
                int num = list.get(i);
                if (i == 0) {
                    cost[i] = cost[i] + num;
                    continue;
                }
                if (i == list.size() - 1) {
                    cost[i] = cost[i - 1] + num;
                    continue;
                }
                cost[i] = Math.min(cost[i], cost[i - 1]) + num;
            }
        }
        int min = 1 << 30;
        for (int i = 0; i <= triangle.size() - 1; i++) {
            min = Math.min(min, cost[i]);
        }
        return min;
    }

    public static void main(String[] args) {
        三角形最小路径和 run = new 三角形最小路径和();
        List<List<Integer>> list = new ArrayList<>();
        list.add(Arrays.asList(2));
        list.add(Arrays.asList(3, 4));
        list.add(Arrays.asList(6, 5, 7));
        list.add(Arrays.asList(4, 1, 8, 3));
        System.out.println(run.minimumTotal(list));
    }
}
